AtCoder ABC 076 C - Dubious Document 2 (300 点)
https://gyazo.com/345a13d493182a71cf8e6356e3611d2c
考察履歴
一度考察の道を誤った後に自力で修正してACさせた
間違いルート
ランレングス圧縮を用いて正規表現パターンを作成
例：?tc???? → .{1,1}t{1}c{1}.{1,4}
正規表現パターンを部分一致で全探索していく←これが普通やらない探索な気がする
ただしパターンの文字数も考慮する必要がある
文字数がtの文字数以上のときのみ判定とした
ACの内容踏まえると、これはよろしくなかったのでは。。。
辞書順最小を求めるので入力$ S'と$ Tは逆順にして、最初のマッチを探すようにした
でpythonのreモジュールをいろいろ使って実装、テストをしたが、WAとりきれず。。 2時間くらい粘った。。
汚いコードになり、考察が誤って気がしてきたので、一旦撤退
正解ルート
$ Tの文字数分の範囲を全探索するのが基本的な考え方
例えば、$ S'=ABCDEFと$ T=CDの場合
$ AB,BC,CD,DE,EFの$ 5パターンのみを比較すれば良い
また$ ?はワイルドカードになるので、これも比較条件にいれる
判定が一致したら、その部分を$ Tで置き換え
残りの$ ?は$ aに置換すれば良い
また、全探索してその結果リストから辞書順最小のものを答え出力してもよいが
私は、入力$ S'と$ Tは逆順にして、最初のマッチを探すようにした
code:python
import sys
import math
import re
sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))
s2 = input()
t = input()
ans_flag = False
for i in range(len(s2)):
for j in range(i+1,len(s2)+1):
if (j-i) == len(t_r):
flag = True
for k,l in enumerate(range(i,j)):
if s2_rl != t_rk and s2_rl != '?': flag = False
if flag == True:
ans = s2_r:i + t_r + s2_rj: ans = ans.replace('?','a')
print(ans)
ans_flag = True
break
else:
continue
break
if ans_flag == False:
print('UNRESTORABLE')
誤った道から正規ルートに戻ってACさせたため学びがいろいろあった。。
考察時点で実装楽だろうと勘違いしたのが痛すぎる。
コード書かないでどれくらいしんどい実装かを素早く判断できる能力が必要。
その前段階として、ちょっと手を動かしてみしんどそうだったら、一旦考察に戻るという勇気が必要。
制約で文字数が少ない時点で、脳死でそっちに行ってよかったのかなぁC問題だし。